Tracking motion of a device across a surface based on images acquired by the device is useful in several applications.
For example, a typical optical mouse today operates by acquiring a series of images as the mouse is moved across a surface (e.g. a desktop). The motion of the optical mouse is tracked using these acquired images. In particular, the optical mouse employs an optical navigation system comprising an image acquisition device which works essentially like a small camera operating at a high frame rate ranging from 1; 500 frames per seconds (fps) to 10,000 fps, with a resolution ranging from 16×16 pixels to 30×30 pixels. FIG. 1 illustrates the components of a typical optical mouse. As shown in FIG. 1, the image acquisition device of the optical mouse comprises a LED 102 (which may alternatively be a Laser) and an image sensor 104 having a pixel array. The LED 102 serves to illuminate the area at which the optical mouse is, so as to allow the image sensor 104 to acquire an image of the area. When the mouse is moved to other areas of the surface, further images of these other areas are acquired in the same manner. FIG. 2 shows two example images acquired successively by an optical mouse as the mouse moves across a surface. From these images, it is possible to determine the displacement of the optical mouse from the area shown in one of the images to the area shown in the other image. Therefore, by acquiring a series of images as the optical mouse is moved to different areas across a surface, the motion of the mouse across the surface can be tracked.
To date, several algorithms for tracking motion of a device from images acquired by the device have been developed. Examples of these are the algorithms developed by Avago, Hewlett-Packard and Microsoft. These prior art algorithms operate by repeatedly estimating the displacement between two images using a single fixed reference image.
Note that in this document, the displacement between two images G and H is a vector and refers to the displacement between the areas g and h respectively shown in the images G and H. The displacement between the areas g and h in turn refers to either the displacement of the area g from the area h, or the displacement of the area h from the area g. Specifically, the notation DGH is used in this document to denote the displacement of the area h shown in the image H from the area g shown in the image G.
The following describes in more detail how the prior art algorithms estimate the displacement between two images.
FIG. 3 shows a series of images (i.e. frames A-Z) acquired by a device as the device moves in a planar motion across a surface. The frames A-Z are acquired successively with frame A being the first acquired frame and frame Z being the last acquired frame. In the prior art algorithms, the displacement between two images is determined by comparing the positions of these images to the position of a single fixed reference image.
For example, to determine the displacement DCD, frame A may be used as the single fixed reference image. In this case, the displacements DAC and DAD are first computed. Then, the displacement DCD is determined by the following Equation (1).DCD=DAD−DAC 
The reason why the prior art algorithms determine the displacement between two images in the above-mentioned way, rather than directly from the positions of the two images, is that sometimes, the two images may not be sufficiently different. More specifically, the shift between the areas shown in the two images may sometimes be so small that it is hard to determine whether there is any shift at all. This usually happens when the movement of the device between acquiring the two images is too small.
There are drawbacks in the above-mentioned approach adopted by the prior art algorithms. For instance, in the above example, if frame A turns out to be an unsuitable reference image because it has a low signal-to-noise ratio, or if the overlap between frames A and D turns out to be insufficiently large to obtain a reliable measure of displacement, then errors are likely to occur in the computation of displacement DAC and/or displacement DAD. This in turn leads to errors in the computation of displacement DCD.
Nevertheless, prior art algorithms to date usually do not aim to achieve high accuracy and low cumulative errors anyway because these are not essential in the current applications utilizing these prior art algorithms. For instance, slight errors in tracking the motion of an optical mouse are usually not noticeable. However, if a more accurate way for tracking the motion of a device from images acquired by the device is available, such motion tracking can be used in many more applications, for example, in print-head displacement measurement, hand-held scanning and device odometry.